package 困难.滑动窗口;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧
 * 移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动
 * 窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sliding-window-maximum
 */
public class 滑动窗口最大值_239 {

    public static void main(String[] args) {

        System.out.println(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));

    }

    /**
     * 滑动窗口+单调栈
     * 1，栈顶元素最大，往后逐渐减小
     * 2，如果当前元素大于栈顶元素，那么当前元素是最优的，栈中的元素全部可以丢弃
     * 只留下当前元素
     * 3，如果当前元素小于栈顶元素，那么栈底部比当前元素小的元素全部可以丢弃
     * 然后将当前元素加入栈底
     * 4，需要判断栈顶元素到当前元素的距离是否 <= k
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            // 去除窗口外的元素
            while (!stack.isEmpty() && i - stack.peekFirst() + 1 > k) {
                stack.pollFirst();
            }
            while (!stack.isEmpty() && nums[stack.peekLast()] < nums[i]) {
                stack.pollLast();
            }

            stack.addLast(i);

            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[stack.peekFirst()];
            }
        }

        return ans;
    }

    /**
     * 优先队列
     * 将 [0,i] 的元素都放入队列中，判断堆顶元素是否在窗口内，
     * 如果不在则取出
     */
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> nums[b] - nums[a]);

        for (int i = 0; i < nums.length; i++) {

            while (!priorityQueue.isEmpty() && i - priorityQueue.peek() + 1 > k) {
                priorityQueue.poll();
            }
            priorityQueue.add(i);

            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[priorityQueue.peek()];
            }
        }

        return ans;
    }

}
